package DFS递归搜索与回溯.二叉树的遍历;


import BFS.层序遍历.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 求根节点到叶子结点数字之和
 */
public class likou129 {

    /**
     * 从根节点到叶子结点数字之和
     */
    // dfs, (详解这个一定要看视频)
//    public int sumNumbers(TreeNode root) {
//        return dfs(root, 0);
//    }

//    public int dfs(TreeNode root, int prev) {
//        prev = prev * 10 + root.val;
//
//        // 递归出口
//        if(root.left == null && root.right == null) {
//            return prev;
//        }
//        // 搞搞左子树, 搞搞右子树
//        int ret = 0;
//        if(root.left != null) ret += dfs(root.left, prev);
//        if(root.right != null) ret += dfs(root.right, prev);
//        return ret;
//    }

    /**
     * 二叉树剪枝
     * @param root
     * @return
     */
//    // 赋予这个递归函数一个任务: 给一个头节点, 就能完成去掉所有子树都是 0 的枝, 返回一个节点
//    public TreeNode pruneTree(TreeNode root) {
//        // 如果是空节点, 直接返回空
//        if(root == null) return null;
//
//        // 主逻辑, 搞搞左子树和右子树
//        if(root.left != null) root.left = pruneTree(root.left);
//        if(root.right != null) root.right = pruneTree(root.right);
//
//        if(root.left == null && root.right == null && root.val == 0)
//            root = null;
//        return root;
//    }

    /**
     * 计算二叉树的布尔值
     * @param root
     * @return
     */
//    public boolean evaluateTree(TreeNode root) {
//        // 函数头已给
//        // 递归出口
//        if(root.left == null) {
//            return root.val == 0 ? false : true;
//        }
//        // 函数体
//        // 相信这个函数, 给一个节点, 就可以返回它的最后的布尔值
//        boolean left = evaluateTree(root.left);
//        boolean right = evaluateTree(root.right);
//
//        return root.val == 2 ? left | right : left & right;
//    }


    /**
     * 验证是否是二叉搜索树
     */
    // dfs
//    long prev = Long.MIN_VALUE; // 要定义为 long. 因为会的范围是 -2 ^ 31 次方. 正好是最小值, 会影响我们的判断
//    public boolean isValidBST(TreeNode root) {
//        // 空树也是一个二叉搜索树
//        if(root == null) return true;
//        // 看看左子树
//        boolean left = isValidBST(root.left);
//        // 看看自己
//        boolean cur = false;
//        if(root.val > prev) cur = true;
//
//        // 不要忘记更新 prev
//        prev = root.val;
//
//        // 看看右子树
//        boolean right = isValidBST(root.right);
//
//        return left && cur && right;
//    }

    /**
     * 找出二叉树中第 k 个小的值
     * @param args
     */
//    int count = 0, ret = 0; // 全局变量, 代码就会很好写
//    public int kthSmallest(TreeNode root, int k) {
//        count = k;
//        dfs(root);
//        return ret;
//        // 错误写法
//        //  if(root == null) return 0;
//        // // 看看左子树
//        // int left = kthSmallest(root.left, k);
//        // count--; ret = left;
//        // if(count == 0) cur = return ret;
//        // count--;
//        // // 看看右子树
//        // int right = kthSmallest(root.right);
//
//        // return ret;
//
//    }
//    // 中序遍历就是一个有序的数组
//    public void dfs(TreeNode root) {
//        if(root == null) return;
//
//        dfs(root.left);
//        count--; // 每次进入循环之后, 减一次就可以.
//        if(count == 0) {
//            ret = root.val;
//            return ;
//        }
//        // 去看看右子树
//        dfs(root.right);
//        // count--; 剪一次就可以了
//        return ;
//    }


    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<>();
        hash.put("startTime", 1);
        hash.put("endTime", 2);
        System.out.println(hash); // { startTime=1, xxx=xxx}
        System.out.println(hash.toString());
    }


}
